#include<bits/stdc++.h>

using namespace std;

#define ll long long
class Solution{
public:
    ll maxScore(vector<int>& nums){
        int n=nums.size(); ll ans=0;
        auto gao=[&](int ban){
            ll g=0,l=1;
            for(int i=0;i<n;i++)
                if(i!=ban){
                    g=gcd(g,nums[i]);
                    l=l/gcd(l,nums[i])*nums[i];
                }
            ans=max(ans,g*l);
        };
        for(int i=-1;i<n;i++) gao(i); return ans;
    }
};

class Solution2{
public:
    int lengthAfterTransformations(string s,int t){
        const int mod=1e9+7; ll cnt[26]={0};
        for(char c:s)cnt[c-'a']++;
        for(int i=1;i<=t;i++){
            int nxt[26]={0};
            for(int j=0;j<25;j++) nxt[j+1]=cnt[j];
            nxt[0]=(nxt[0]+cnt[25])%mod;
            nxt[1]=(nxt[1]+cnt[25])%mod;
            for(int j=0;j<26;j++)cnt[j]=nxt[j];
        }
        ll ans=0;
        for(int i=0;i<26;i++)ans=(ans+cnt[i])%mod;
        return ans;
    }
};

// greedy
class Solution3{
public:
    int subsequencePairCount(vector<int>& nums){
        int n=nums.size(), mx=0;
        for(int x: nums) mx=max(mx,x);
        const int mod=1e9+7; ll f[2][mx+1][mx+1];
        memset(f,0,sizeof(f)); f[0][0][0]=1;
        auto update=[&](ll &a, ll b){a=(a+b)%mod;};
        for(int i=1;i<=n;i++){
            int x=nums[i-1];
            for(int j=0;j<=mx;j++)for(int k=0;k<=mx;k++)f[i&1][j][k]=0;
            for(int j=0;j<=mx;j++)for(int k=0;k<=mx;k++){
                update(f[i&1][gcd(j,x)][k],f[i&1^1][j][k]);
                update(f[i&1][j][gcd(k,x)],f[i&1^1][j][k]);
                update(f[i&1][j][k], f[i&1^1][j][k]);
            }
        }
        ll ans=0;
        for(int j=1;j<=mx;j++) update(ans,f[n&1][j][j]);
        return ans;
    }
};

// matrix fast exponotial
#define MOD ((int) 1e9 + 7)
struct Matrix {
    int n, m;
    long long A[26][26];

    Matrix(int n, int m): n(n), m(m) { memset(A, 0, sizeof(A)); }

    Matrix operator*(const Matrix &o) const {
        Matrix r(n, o.m);
        for (int k = 0; k < m; k++) for (int i = 0; i < n; i++) for (int j = 0; j < o.m; j++)
                    r.A[i][j] = (r.A[i][j] + A[i][k] * o.A[k][j]) % MOD;
        return r;
    }
};
Matrix power(Matrix a, ll b){
    Matrix y(a.n,a.m);
    for(int i=0;i<y.n;i++) y.A[i][i]=1;
    for(;b;b>>=1){
        if(b&1) y=y*a;
        a=a*a;
    } return y;
}
class Solution4 {
public:
    int lengthAfterTransForamtions(string s,int t,vector<int>&nums){
        Matrix k(26,26);
        for(int i=0;i<26;i++)for(int j=1;j<=nums[i];j++) k.A[i][(i+j)%26]=1;
        k=power(k,t);
        Matrix v(1,26);
        for(char c: s) v.A[0][c-'a']++;
        v=v*k;
        ll ans=0;
        for(int i=0;i<26;i++)ans=(ans+v.A[0][i])%MOD;
        return ans;
    }
};

int main(){
    Solution s; vector<int> nums1={2,4,8,16}; cout<<s.maxScore(nums1)<<endl;
    Solution2 s2; cout<<s2.lengthAfterTransformations("abcyy",2)<<endl;
    vector<int> nums3={1,2,3,4};
    Solution3 s3; cout<<s3.subsequencePairCount(nums3)<<endl;
    vector<int> nums4={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2};
    Solution4 s4; cout<<s4.lengthAfterTransForamtions("abcyy",2,nums4)<<endl;
}